package leetcode.code1482;

import java.util.Arrays;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public int minDays(int[] bloomDay, int m, int k) {
		if (m * k > bloomDay.length) {
			return -1;
		}
		int r = Arrays.stream(bloomDay).max().getAsInt();
		int l = 1;
		int ans = -1;
		while (l <= r) {
			int cur = ((r - l) >> 1) + l;
			int s = this.f(bloomDay, cur, k);
			if (s >= m) {
				ans = cur;
				r = cur - 1;
			} else {
				l = cur + 1;
			}

		}
		return ans;
	}

	private int f(int[] b, int max, int k) {
		int r = 0, len = b.length, cnt = 0;
		int ans = 0;
		while (r < len) {
			cnt = 0;
			while (r < len && b[r] <= max && cnt < k) {
				r++;
				cnt++;
			}
			if (cnt == k) {
				ans++;
			}
			while (r < len && b[r] > max) {
				r++;
			}
		}
		return ans;
	}

	@Override
	public void debug4() {
		H.compare(3, this.minDays(H.str2array3("[1,10,3,10,2]"), 3, 1));
		H.compare(-1, this.minDays(H.str2array3("[1,10,3,10,2]"), 3, 2));
		H.compare(12, this.minDays(H.str2array3("[7,7,7,7,12,7,7]"), 2, 3));
		H.compare(1000000000, this.minDays(H.str2array3("[1000000000,1000000000]"), 1, 1));
		H.compare(9, this.minDays(H.str2array3("[1,10,2,9,3,8,4,7,5,6]"), 4, 2));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
